package me.winter.imgop;

// Creates a histogram of the pixel values in a pixel array and provides
// methods to access this data.  This histogram class is designed to handle
// pixel array that contain values in ranges larger than 0 to 255 including
// possible negative brightness values.
public class Histogram {
    // The range of brightness values in the pixel array passed to the constructor
    private int max, min;

    // The array of count values for different brightness values
    private int [] hist;
    
    // The total number of values in the pixel array passed to the constructor
    private int tot;
    
    // Create a histogram from a given pixel array
    public Histogram( int[][] source ) {
        // Save the number of elements in the pixel array
        tot = source.length*source[0].length;
        
       // Determine the minimum and maximum brightness values in the array;
        max = min = source[0][0];
        for ( int x = 0; x < source.length; x++ ) {
          for ( int y = 0; y < source[0].length; y++ ) {
                  min = Math.min(source[x][y],min);
                  max = Math.max(source[x][y],max);
            }
        }
        
        
        // Create an array with one entry for each value between min and max
        // equal to the number of pixels in the image with the corresponding
        // brightness value
        hist = new int[max - min + 1];
        for ( int x = 0; x < source.length; x++ ) {
          for ( int y = 0; y < source[0].length; y++ ) {
                  hist[ source[x][y] - min ] ++;
            }
        }
    }
    
    // Get the size of the range of values found in the pixel array
    public int range() {
        return hist.length;
    }
    
    // Get the number of elements in the pixel array
    public int total() {
        return tot;
    }
    
    // Get the count of the number of times a particular shade of brightness
    // occurs in the pixel array used to build the histogram.
    public int frequency( int shade ) {
        return hist[ shade - min ];
    }
    
    // Get the count of the number of times the most frequently found shade of
    // brightness occurs in the pixel array used to build the histogram
    public int maxFreq() {
        int max = hist[0];
        for ( int i = 1; i < hist.length; i++ ) {
            max = Math.max( max, hist[i] );
        }
        return max;
    }
    
    // Get the largest brightness value found in the source pixel array
    public int max() {
        return max;
    }
    
    // Get the smallest brightness value found in the source pixel array
    public int min() {
        return min;
    }
    
    // Get the number of bits that would be required per pixel to encode this
    // image if it were encoded using a Huffman code designed for this
    // particular image.
    public double huffmanSize( ) {
        int [] weights = new int[hist.length];
        int distinct = 0;
        int min, nextToMin, totalBitsUsed = 0;
        // Copy all non-zero entries of histogram array into weights array
        for (int i = 0; i < hist.length; ++i) {
            if (hist[i] != 0) {
                weights[distinct++] = hist[i];
            }
        }

        while (distinct > 1) {
            min = extractMin(weights, distinct--);
            nextToMin = extractMin(weights, distinct--);
            weights[++distinct - 1] = min + nextToMin;
            totalBitsUsed += min + nextToMin;
        }
        
        return (double)totalBitsUsed / tot;
    }
        
    // Return the index of minimum value in weights
    public int findMin(int[] weights, int distinct) {
        int minIndex = 0;

        for (int i = 1; i < distinct; ++i)
            if (weights[i] < weights[minIndex])
                minIndex = i;

        return minIndex;
    }
    
    // Return an integer representing the minimum weight.
    // Notice that extractMin does not itself decrement distinct,
    // you will have to do that yourself after calling extractMin
    public int extractMin(int[] weights, int distinct) {
        int minIndex = findMin(weights, distinct);
        int min = weights[minIndex];

        weights[minIndex] = weights[distinct - 1];

        return min;   
    }
    
}